package linkedlist;

import java.util.*;

/**
 * https://leetcode.cn/problems/sort-list/?favorite=2cktkvj
 * 148 排序链表
 */
public class SortList {
    class Solution {
        public ListNode sortList(ListNode head) {
            if (head == null || head.next == null) {
                return head;
            }
            List<ListNode> list = new ArrayList<>();
            ListNode cur = head;
            while (cur != null) {
                list.add(cur);
                cur = cur.next;
            }
            ListNode[] array = new ListNode[list.size()];
            int index = 0;
            for (ListNode node : list) {
                array[index++] = node;
            }
            Comparator comparator = new Comparator<ListNode>() {
                @Override
                public int compare(ListNode o1, ListNode o2) {
                    return Integer.compare(o1.val, o2.val);
                }
            };
            Arrays.sort(array, comparator);
            for (int i = 0; i < array.length - 1; i++) {
                array[i].next = array[i + 1];
            }
            return array[0];
        }
    }
}
